#pragma once

/*
 * a simple allocator library, implement:
 *	template<typename T>
 *	simple_alloc
 *		void* allocate(size_t,void*);
 *		void deallocate(void*, size_t);
 *		void destroy(T*);
 *		void construct(T1*,const T2&);
 */

#include <cstddef>
#include <iostream>
#include <new>
#include <cstdlib>

#define _USE_DEFAULT_MALLOC_ // 使用二级配置器

#ifndef _THROW_BAD_ALLOC_
#define _THROW_BAD_ALLOC_                      \
	std::cerr << "out of memory" << std::endl; \
	exit(1);
#endif // !_THROW_BAD_ALLOC_

namespace myallocator
{

	// iterator_traits 用于萃取出iterator中的关联类型
	template <class T>
	struct Iterator_traits
	{
		using value_type = typename T::value_type;
	};
	// 特例化 iterator_traits
	template <class T>
	struct Iterator_traits<T *>
	{
		using value_type = T;
	};
	// 取出iterator中的value_type
	template <typename T>
	typename Iterator_traits<T>::value_type *value_type(T value)
	{
		return static_cast<typename Iterator_traits<T>::value_type *>(0);
	}

	// 用于表示type中是否存在或不存在trivial
	struct _false_type
	{
	};
	struct _true_type
	{
	};

	// type_traits 萃取出type是否有各种默认构造、析构、操作符重载等
	template <class Type>
	struct _type_traits
	{
		using has_trivial_default_constructor = _false_type;
		using has_trivial_copy_constructor = _false_type;
		using has_trivial_assignment_operator = _false_type;
		using has_trivial_default_destructor = _false_type;
		using is_POD_type = _false_type;
	};

	// constructor
	template <class T1, class T2>
	inline void construct(T1 *p, const T2 &value)
	{
		new (p) T1(value);
	}

	// 第一版destroy函数
	template <class T>
	inline void destroy(T *ptr)
	{
		ptr->~T();
	}

	// 有 trivial destructor 的情况
	template <class ForwardIterator>
	inline void _destroy_aux(ForwardIterator first, ForwardIterator last, _true_type) { /*默认构造函数，无需调用destroy（PS:析构函数主要用于释放heap中内存）*/ }

	// 有 non-trivial destructor 的情况
	template <class ForwardIterator>
	inline void _destroy_aux(ForwardIterator first, ForwardIterator last, _false_type)
	{
		for (; first < last; first++)
		{
			destroy(*&first); // 可能申请堆内存，需要释放内存
		}
	}

	// 中间封装一层，使用traits萃取出has_trivial_default_destructor的值，通过该值调用不同的_destroy_aux函数
	template <class ForwardIterator, class T>
	inline void _destroy(ForwardIterator first, ForwardIterator last, T *)
	{
		_destroy_aux(first, last, typename _type_traits<T>::has_trivial_default_destructor());
	}

	// 第二版destroy函数
	template <class ForwardIterator>
	inline void destroy(ForwardIterator first, ForwardIterator last)
	{
		_destroy(first, last, value_type(first));
	}

	// 第一级配置器
	template <int inst = 0>
	class _malloc_alloc_template
	{
		// 以下为函数指针，用于处理分配失败的情况
	private:
		// oom：out of memory
		static void *oom_malloc(size_t);
		static void *oom_reaclloc(void *, size_t);
		static void (*_malloc_alloc_oom_handler)();

	public:
		// allocate，第一级只使用malloc进行分配内存,失败则调用oom_malloc
		static void *allocate(size_t n)
		{
			void *result = malloc(n);
			if (result == 0)
				result = oom_malloc(n);
			return result;
		}

		// deallocate，简单使用free进行内存释放
		static void deallocate(void *ptr, size_t /* n */)
		{
			free(ptr);
		}

		// 直接使用realloc分配内存，失败则调用处理函数oom_realloc()
		static void *reallocate(void *ptr, size_t new_size)
		{
			void *result = realloc(ptr, new_size);
			if (result == 0)
				result = oom_reaclloc(ptr, new_size);
			return result;
		}

		// 仿真set_new_handler，即可以指定自己的out_of_memory_handler,挺复杂的对吧emmmmm
		static void (*set_malloc_handler(void (*f)()))()
		{
			void(*old) = _malloc_alloc_oom_handler;
			_malloc_alloc_oom_handler = f;
			return (old);
		}
	};
	// 初始化指针值为0
	template <int inst>
	void (*_malloc_alloc_template<inst>::_malloc_alloc_oom_handler)() = 0;

	// malloc失败处理函数，循环调用oom_handler，直到malloc成功
	template <int inst>
	void *_malloc_alloc_template<inst>::oom_malloc(size_t new_size)
	{
		void (*my_malloc_handler)();
		void *result;
		for (;;)
		{
			my_malloc_handler = _malloc_alloc_oom_handler;
			if (my_malloc_handler == 0)
			{ // 未初始化，则直接退出程序
				_THROW_BAD_ALLOC_;
			}
			result = malloc(new_size);
			if (result)
				return result;
		}
	}

	// realloc失败处理函数，原理同malloc
	template <int inst>
	void *_malloc_alloc_template<inst>::oom_reaclloc(void *ptr, size_t new_size)
	{
		void (*my_malloc_handler)();
		void *result;
		for (;;)
		{
			my_malloc_handler = _malloc_alloc_oom_handler;
			if (my_malloc_handler == 0)
			{
				_THROW_BAD_ALLOC_;
			}
			result = realloc(ptr, new_size);
			if (result)
				return result;
		}
	}

	// 第二级配置器 需要注意最小的块（_ALIGN）的size至少要比obj大，否则存不下obj
	// 缺陷：对于小于_ALIGN的块会至少分配_ALIGN的大小，造成内存浪费，比如：会给int分配8B，目前还没找到好办法解决
	enum
	{
		_ALIGN = 8
	}; // 小型块上调边界
	enum
	{
		_MAX_BYTES = 128
	}; // 小型块上界
	enum
	{
		_NFREELISTS = _MAX_BYTES / _ALIGN
	}; // free-lists的个数

	
	template <bool threads = false, int inst = 0>
	class _default_alloc_template
	{
	private:
		// 传入bytes，将bytes上调为8的倍数，如7->8
		static size_t ROUND_UP(size_t bytes)
		{
			return ((bytes + _ALIGN - 1) / _ALIGN) * _ALIGN;
			// return (bytes + _ALIGN - 1) & ~(_ALIGN - 1);
		}

	private:
		union obj
		{ // free-lists的结点构造
			union obj *free_list_link;
			char client_data[1];
		};

	private:
		// 16个free-list
		static obj *volatile free_list[_NFREELISTS];
		// 根据传入的bytes，查找其所需的最小free-list
		static size_t FREELIST_INDEX(size_t bytes)
		{
			return (bytes + _ALIGN - 1) / _ALIGN - 1;
		}

		// 返回一个大小为n的对象，并且可能添加大小为n的其他块到free-list中
		static void *refill(size_t size);

		// 申请大小为nobjs*n的块，如果空间不足，申请的块会变小
		static char *chunk_alloc(size_t size, int &nobjs);

		// chunk allocation state
		static char *start_free; // 内存池开始位置
		static char *end_free;	 // 内存池结束位置
		static size_t heap_size; // 已分配的堆大小

	public:
		static void *allocate(size_t n);
		static void deallocate(void *ptr, size_t n);
		static void *reallocate(void *ptr, size_t old_size, size_t new_size);
	};

	// 初始化
	template <bool threads, int inst>
	char *_default_alloc_template<threads, inst>::start_free = 0;

	template <bool threads, int inst>
	char *_default_alloc_template<threads, inst>::end_free = 0;

	template <bool threads, int inst>
	size_t _default_alloc_template<threads, inst>::heap_size = 0;

	template <bool threads, int inst>
	typename _default_alloc_template<threads, inst>::obj *volatile _default_alloc_template<threads, inst>::free_list[_NFREELISTS] =
		{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

	// 分配函数
	template <bool threads, int inst>
	void *_default_alloc_template<threads, inst>::allocate(size_t n)
	{
		if (n > size_t(_MAX_BYTES))
		{ // 大于128B，交给第一级配置器
			return _malloc_alloc_template<inst>::allocate(n);
		}
		// 小于128B，交给第二级配置器
		obj *volatile *my_free_list = free_list + FREELIST_INDEX(n); // 得到free_list
		obj *result;
		result = *my_free_list;
		if (result == 0)
		{ // free_list无内存块，调用refill填充内存块
			/*
				传入refill的n需要用ROUND_UP处理，否则可能会内存冲突
				不信把ROUND_UP去掉，_ALIGN取8，用vector<int,simple_alloc<int>>试试
				最好是打开内存
			*/
			void *r = refill(ROUND_UP(n));
			return r;
		}
		// free_list中有内存块，调整free_list
		*my_free_list = result->free_list_link;
		return result;
	}

	// 从内存中取出nobjs*size大小的内存块，如果空间不足，可能取出的内存块比较小
	template <bool threads, int inst>
	void *_default_alloc_template<threads, inst>::refill(size_t size)
	{
		int nobjs = 20;
		char *result = chunk_alloc(size, nobjs);
		// 只返回了一个大小为size的内存块，直接返回给调用者
		if (nobjs == 1)
		{
			return result;
		}
		/*
		返回一个 nobjs*size 大小的内存块，将这个内存块分割成nobjs个大小为size的内存块
		其中一个返回给调用者，其他的用链表的形式存储到free_list中
		*/
		obj *volatile *my_free_list = free_list + FREELIST_INDEX(size); // 大小为size的内存块所在链表
		obj *current_obj = (obj *)result;
		obj *next_obj = (obj *)((char *)current_obj + size); // 指向第二个块，第一个块被返回给调用者
		*my_free_list = next_obj;
		// 将nobjs-1个大小为size的内存块存入my_free_list中
		for (int n = 1;; n++)
		{
			current_obj = next_obj;
			next_obj = (obj *)((char *)current_obj + size);
			if (n == nobjs - 1)
			{
				current_obj->free_list_link = 0;
				break;
			}
			current_obj->free_list_link = next_obj;
		}
		return result;
	}

	// 从线程池中取出空间给free_list使用
	template <bool threads, int inst>
	char *_default_alloc_template<threads, inst>::chunk_alloc(size_t size, int &nobjs)
	{
		char *result;
		size_t total_size = nobjs * size;
		size_t bytes_left = end_free - start_free;
		if (bytes_left >= total_size)
		{ // 内存池中的空间 >=nobjs*size
			result = start_free;
			start_free += total_size;
			return result;
		}
		else if (bytes_left >= size)
		{ // size<= 内存池中的空间 <=nobjs*size，返回尽可能大的块
			nobjs = bytes_left / size;
			result = start_free;
			start_free += nobjs * size;
			return result;
		}
		else
		{ // 内存池中的空间不足了
			// 将剩余的内存块存入free_list中
			if (bytes_left > 0)
			{
				obj *volatile *my_free_list = free_list + FREELIST_INDEX(bytes_left);
				obj *p = (obj *)start_free;
				p->free_list_link = *my_free_list;
				*my_free_list = p;
			}
			// 申请一块更大的内存
			size_t bytes_to_get = 2 * total_size + ROUND_UP(heap_size >> 4);
			start_free = (char *)malloc(bytes_to_get);
			if (start_free == 0)
			{ // 申请失败
				// 在free_list查找是否存在比size更大的块
				for (int i = size; i < _MAX_BYTES; i += _ALIGN)
				{
					obj *volatile *my_free_list = free_list + FREELIST_INDEX(i);
					if (*my_free_list != 0)
					{ // 找到比size更大的块
						// 将大小为i的块逻辑上拆成两部分，一部分大小为size，返回调用者，另一部分为i-size，重新加入free_list中
						start_free = (char *)(*my_free_list);
						end_free = start_free + size;
						*my_free_list = (*my_free_list)->free_list_link;
						return chunk_alloc(size, nobjs);
					}
				}
				// 查找失败
				// 调整end_free，调用第一级的分配器，希望oom_malloc_handler可以帮忙处理
				end_free = 0;
				start_free = (char *)_malloc_alloc_template<inst>::allocate(bytes_to_get);
			}
			// 申请成功，调整 heap_size、end_free
			// 递归调用chunk_alloc，此时的start_free-end_free已经足够分配一块nobjs*size的内存块
			heap_size += bytes_to_get;
			end_free = start_free + bytes_to_get;
			return chunk_alloc(size, nobjs);
		}
	}

	template <bool threads, int inst>
	void _default_alloc_template<threads, inst>::deallocate(void *ptr, size_t n)
	{
		if (n > size_t(_MAX_BYTES))
		{ // 大于128B，交给第一级配置器
			_malloc_alloc_template<inst>::deallocate(ptr, n);
			return;
		}
		// 小于128B，交给第二级配置器
		obj *volatile *my_free_list = free_list + FREELIST_INDEX(n); // 找到 n Bytes 对应的free_list
		obj *p = (obj *)ptr;										 // 将void*装换为obj*
		// 将该块添加入线程池
		p->free_list_link = *my_free_list;
		*my_free_list = p;
	}

	template <bool threads, int inst>
	void *_default_alloc_template<threads, inst>::reallocate(void *ptr, size_t old_size, size_t new_size)
	{
		return nullptr;
	}

	// simple_alloc
	template <class T>
	class simple_alloc
	{
	public:
		using pointer = T *;
		using const_pointer = const T *;
		using reference = T &;
		using const_reference = const T &;
		using difference_type = ptrdiff_t;
		using value_type = T;
		using size_type = size_t;

		simple_alloc() = default;
		simple_alloc(const simple_alloc<T> &alloc) = default;

		// 泛化的copy构造，什么都不做，参考std::allocator<T>的实现
		template <class U>
		simple_alloc(const simple_alloc<U> &)
		{
			int n = sizeof(U);
		};
		~simple_alloc() = default;

		// STL规定的格式，这样写就行。
		// 比如 ：在vector中指定_Alloc为simple_alloc则在构造函数调用时会用到rebind
		template <class U>
		struct rebind
		{
			using other = simple_alloc<U>;
		};

		// 分配size个T对象的内存空间
		// 使用这玩意初始化vector，在调用vector构造函数的时候不论T为什么类型，
		//_Alloc_proxy函数中_Container_proxy* const _New_proxy = _Unfancy(_Al.allocate(1)) 时会调用该函数，
		// 不过奇怪的是这时的T大小为8或者16？，反正不是自定义的类型大小，可能此时调用的allocator还没 rebind?
		pointer allocate(size_t size, void * = 0)
		{

#ifndef _USE_DEFAULT_MALLOC_
			return (pointer)_malloc_alloc_template<>::allocate(size * sizeof(T));
#endif // !_USE_DEFAULT_MALLOC_

			return (pointer)_default_alloc_template<>::allocate(size * sizeof(T));
		}

		// 用x构造p
		void construct(pointer p, const T &x)
		{
			myallocator::construct(p, x);
		}

		// 析构p
		void destroy(pointer p)
		{
			myallocator::destroy(p);
		}

		// 释放p所指内存空间
		void deallocate(pointer p, size_t size)
		{

#ifndef _USE_DEFAULT_MALLOC_
			return _malloc_alloc_template<>::deallocate(p, size);
#endif // !_USE_DEFAULT_MALLOC_

			return _default_alloc_template<>::deallocate(p, size);
		}

		// 获得x的地址
		pointer address(reference x) const
		{
			return &x;
		}
		const_pointer address(const_reference x) const
		{
			return &x;
		}

		// 最多可以容纳的T数量
		size_type max_size()
		{
			return (size_type)INT_MAX / sizeof(T);
		}
	};
}